Termination w.r.t. Q proof of /tmp/tmp-MvikC/4.02.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.

↳ QTRS

  ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.

Using Dependency Pairs [1,15] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), z), x)
*¹(*(i(x), k(y, z)), x) → K(*(*(i(x), y), x), *(*(i(x), z), x))
I(*(x, y)) → I(x)
*¹(x, *(y, z)) → *¹(x, y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), z)
I(*(x, y)) → *¹(i(y), i(x))
*¹(x, *(y, z)) → *¹(*(x, y), z)
*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), y), x)
I(*(x, y)) → I(y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), y)

The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), z), x)
*¹(*(i(x), k(y, z)), x) → K(*(*(i(x), y), x), *(*(i(x), z), x))
I(*(x, y)) → I(x)
*¹(x, *(y, z)) → *¹(x, y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), z)
I(*(x, y)) → *¹(i(y), i(x))
*¹(x, *(y, z)) → *¹(*(x, y), z)
*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), y), x)
I(*(x, y)) → I(y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), y)

The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 2 SCCs with 2 less nodes.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

          ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), z), x)
*¹(x, *(y, z)) → *¹(x, y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), z)
*¹(x, *(y, z)) → *¹(*(x, y), z)
*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), y), x)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), y)

The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [15].

The following pairs can be oriented strictly and are deleted.

*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), z), x)
*¹(x, *(y, z)) → *¹(x, y)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), z)
*¹(x, *(y, z)) → *¹(*(x, y), z)
*¹(*(i(x), k(y, z)), x) → *¹(*(i(x), y), x)
*¹(*(i(x), k(y, z)), x) → *¹(i(x), y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
*¹(x1, x2) = *¹(x1, x2)
*(x1, x2) = *(x1, x2)
i(x1) = i(x1)
k(x1, x2) = k(x1, x2)
1 = 1

Recursive path order with status [2].
Quasi-Precedence:

i₁ > [*^1₂, *₂] > [k₂, 1]

Status:

i₁: [1]
*^1₂: [2,1]
k₂: [1,2]
*₂: [2,1]
1: multiset

The following usable rules [17] were oriented:

*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(x, 1) → x
*(i(x), x) → 1
*(1, y) → y
*(x, *(y, z)) → *(*(x, y), z)
*(x, i(x)) → 1
*(*(x, y), i(y)) → x
i(1) → 1
i(i(x)) → x
*(*(x, i(y)), y) → x
k(x, 1) → 1
i(*(x, y)) → *(i(y), i(x))

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

            ↳ QDPOrderProof

              ↳ QDP

                ↳ PisEmptyProof

          ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

I(*(x, y)) → I(x)
I(*(x, y)) → I(y)

The TRS R consists of the following rules:

*(x, 1) → x
*(1, y) → y
*(i(x), x) → 1
*(x, i(x)) → 1
*(x, *(y, z)) → *(*(x, y), z)
i(1) → 1
*(*(x, y), i(y)) → x
*(*(x, i(y)), y) → x
i(i(x)) → x
i(*(x, y)) → *(i(y), i(x))
k(x, 1) → 1
k(x, x) → 1
*(k(x, y), k(y, x)) → 1
*(*(i(x), k(y, z)), x) → k(*(*(i(x), y), x), *(*(i(x), z), x))
k(*(x, i(y)), *(y, i(x))) → 1

Q is empty.
We have to consider all minimal (P,Q,R)-chains.
We can use the usable rules and reduction pair processor [15] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its argument. Then, we can delete all non-usable rules [17] from R.

↳ QTRS

  ↳ DependencyPairsProof

    ↳ QDP

      ↳ DependencyGraphProof

        ↳ AND

          ↳ QDP

          ↳ QDP

            ↳ UsableRulesProof

              ↳ QDP

                ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

I(*(x, y)) → I(x)
I(*(x, y)) → I(y)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:

I(*(x, y)) → I(x)
The graph contains the following edges 1 > 1
I(*(x, y)) → I(y)
The graph contains the following edges 1 > 1